package graph;

import java.util.*;

public class Graph {
    private Map<String,Integer> vertexNameIndexMap;
    private Map<Integer,String> vertexIndexNameMap;
    private int[][] graphData;
    private int numOfEdges;
    private int numOfVertex;
    private int vertexTotalNum;
    private ArrayList<Edge> edgeList;
    private final static int MAX_WEIGHT=65536;    //表示不连通
    public Graph(int vertexTotalNum) {
        vertexNameIndexMap = new HashMap<>();
        vertexIndexNameMap = new HashMap<>();
        graphData = new int[vertexTotalNum][vertexTotalNum];
        edgeList = new ArrayList<>();
        for (int i=0;i<graphData.length;i++){
            Arrays.fill(graphData[i],MAX_WEIGHT);
            graphData[i][i]=0;
        }
        this.vertexTotalNum = vertexTotalNum;
        numOfVertex = 0;
        numOfEdges = 0;
    }

    public int getNumOfEdges() {
        return numOfEdges;
    }

    public int getNumOfVertex() {
        return numOfVertex;
    }

    public int getVertexTotalNum() {
        return vertexTotalNum;
    }

    private void convertNameIndexMap(){
        Set<String> set = vertexNameIndexMap.keySet();
        for(String key: set){
            vertexIndexNameMap.put(vertexNameIndexMap.get(key),key);
        }
    }
    public void addVertex(String vertexName){
        if(vertexNameIndexMap.get(vertexName)!=null){
            return;
        }
        if(numOfVertex<vertexTotalNum){
            vertexNameIndexMap.put(vertexName,numOfVertex++);
            if(numOfVertex==vertexTotalNum){
                convertNameIndexMap();
            }
        }
    }
    public void printGraphData(){
        for(int[] a:graphData){
            System.out.println(Arrays.toString(a));
        }
    }
    public void addEdge(String edge1,String edge2,int weight){
        Integer index1 = vertexNameIndexMap.get(edge1);
        Integer index2 = vertexNameIndexMap.get(edge2);
        if(index1!=null&&index2!=null){
            graphData[index1][index2] = weight;
            graphData[index2][index1] = weight;
            edgeList.add(new Edge(edge1,edge2,weight));
            numOfEdges++;
        }
    }
    private void dfsStep(boolean[] isVisited,int index){
        isVisited[index] = true;
        System.out.print(vertexIndexNameMap.get(index)+"->");
        for(int i=0;i<vertexTotalNum;i++){
            if(graphData[index][i]!=0&&isVisited[i]==false){
                dfsStep(isVisited,i);
            }
        }
    }

    public void dfs(String startVertex){
        boolean[] isVisited = new boolean[vertexTotalNum];
        Integer index = vertexNameIndexMap.get(startVertex);
        if(index==null){
            return;
        }
        dfsStep(isVisited,index);
        System.out.println();
    }

    private void bfsStep(boolean[] isVisited,int index){
        Queue<Integer> queue = new LinkedList<>();
        for(int i=0;i<vertexTotalNum;i++){
            if(graphData[index][i]!=0&&isVisited[i]==false){
                isVisited[i] = true;
                System.out.print(vertexIndexNameMap.get(i)+"->");
                queue.add(i);
            }
        }
        while(queue.peek()!=null){
            bfsStep(isVisited,queue.poll());
        }
    }
    public void bfs(String startVertex){
        boolean[] isVisited = new boolean[vertexTotalNum];
        Integer index = vertexNameIndexMap.get(startVertex);
        if(index==null){
            return;
        }
        System.out.print(startVertex+"->");
        isVisited[index] = true;
        bfsStep(isVisited,index);
        System.out.println();
    }

    public void primSmallestTree(String startVertex){
        Integer index = vertexNameIndexMap.get(startVertex);
        if(index==null){
            return;
        }
        int minWeight = MAX_WEIGHT;
        int v1 = -1;
        int v2 = -1;
        boolean[] isVisited = new boolean[vertexTotalNum];
        isVisited[index] = true;
        for(int i=1;i<numOfVertex;i++){
            for(int j=0;j<numOfVertex;j++){
                for(int k=0;k<numOfVertex;k++){
                    if(isVisited[j]&&!isVisited[k]&&graphData[j][k]<minWeight){
                        minWeight = graphData[j][k];
                        v1=j;
                        v2=k;
                    }
                }
            }
            isVisited[v2] = true;
            System.out.println("<"+vertexIndexNameMap.get(v1)+","+vertexIndexNameMap.get(v2)+">"+" weight:"+graphData[v1][v2]);
            minWeight=MAX_WEIGHT;
        }
    }
    public void kruskalSmallestTree(){
        ArrayList<Edge> smallestTreeEdges = new ArrayList<>();
        edgeList.sort(new Comparator<Edge>() {
            @Override
            public int compare(Edge o1, Edge o2) {
                return o1.compareTo(o2);
            }
        });
        int[] ends = new int[numOfVertex];
        Arrays.fill(ends,-1);
        for(int i=0;i<edgeList.size();i++){
            Edge edge = edgeList.get(i);
            int start = vertexNameIndexMap.get(edge.getStart());
            int end = vertexNameIndexMap.get(edge.getEnd());
            int m = getEnd(ends,start);
            int n = getEnd(ends,end);
            if(m!=n){
                smallestTreeEdges.add(edge);
                ends[m] = n;
            }
        }
        for (Edge e:smallestTreeEdges){
            System.out.println("<"+e.getStart()+","+e.getEnd()+">"+" weight:"+e.getWeight());
        }
    }

    private int getEnd(int[] ends, int i) {
        while(ends[i]!=-1){
            i = ends[i];
        }
        return i;
    }

    public void dijkstra(String start){
        Integer si = vertexNameIndexMap.get(start);
        if(si==null){
            return;
        }
        int[] distance = new int[numOfVertex];
        int[] pre = new int[numOfVertex];
        boolean[] isVisited = new boolean[numOfVertex];
        Arrays.fill(distance,Integer.MAX_VALUE);
        distance[si]=0;
        isVisited[si]=true;
        pre[si] = si;
        int index=1;
        //特殊！记录与起点直连的所有点距离
        for(int i=0;i<numOfVertex;i++){
            if(graphData[si][i]<distance[i]){
                distance[i] = graphData[si][i];
                pre[i] = si;
            }
        }
        for(int i=1;i<numOfVertex;i++){
            int min = Integer.MAX_VALUE;
            for(int j=0;j<numOfVertex;j++){
                if(!isVisited[j] && distance[j]<min){
                    min = distance[j];
                    index = j;
                }
            }
            isVisited[index] = true;

            for(int j=0;j<numOfVertex;j++){
                if(!isVisited[j]){
                    int length = graphData[index][j]+distance[index];
                    if(length<distance[j]){
                        distance[j] = length;
                        pre[j] = index;
                    }
                    //distance[j] = Math.min(graphData[index][j]+distance[index],distance[j]);
                }
            }
        }
        for (int i=0;i<numOfVertex;i++){
            System.out.print(start+"->"+vertexIndexNameMap.get(i)+" distance:"+distance[i]);
            System.out.print(" path:");
            printPath(pre,i,si);
            System.out.println();
        }
    }
    private void printPath(int[] pre,int i,int si){
        if(i==si){
            System.out.print(vertexIndexNameMap.get(i));
            return;
        }
        printPath(pre,pre[i],si);
        System.out.print("->"+vertexIndexNameMap.get(i));
    }
    public void floyd(String start){
        Integer si = vertexNameIndexMap.get(start);
        if(si==null){
            return;
        }
        int[][] distance = new int[numOfVertex][];
        int[][] pre = new int[numOfVertex][numOfVertex];
        for(int i=0;i<numOfVertex;i++){
            distance[i] = Arrays.copyOf(graphData[i],graphData[i].length);
            Arrays.fill(pre[i],i);
        }
        for(int i=0;i<numOfVertex;i++){
            for (int j=0;j<numOfVertex;j++){
                for (int k=0;k<numOfVertex;k++){
                    int length = distance[j][i]+distance[i][k];
                    if(length<distance[j][k]){
                        distance[j][k] = length;
                        pre[j][k] = pre[i][k];
                    }
                }
            }
        }
        for(int i=0;i<numOfVertex;i++){
            System.out.println(distance[si][i]);
            printPath(pre[si],i,si);
            System.out.println();
        }

    }
}
